In recent years, standards have been developed for the transport of broadband communications. Among these are the Synchronous Optical Network (SONET) and the similar Synchronous Digital Hierarchy (SDH). The expected growth in synchronous transport facilities based on SONET and SDH supports a need for more efficient synchronous switch fabric architectures. The modular byte-interleaved structure of SONET is based on Synchronous Transport Signal level 1, or STS-1, format, in which overhead plus payload results in a rate of 51.840 Mb/s. The STS-1 frame consists of 90 columns by 9 rows of bytes, or 810 bytes, with a frame rate of 125 .mu.s. The first three columns in the frame are devoted to transport overhead (TOH), while the remaining 87 columns carry the payload, including one column devoted to path overhead (POH). 87 columns of payload constitute a Synchronous Payload Envelope (SPE). However, an SPE can cross frame boundaries, and is allowed to float anywhere within the payload-carrying portion of one or more contiguous frames to accommodate the semi-synchronous nature of the transport facilities. For switching of rates below the STS-1 rate, a switch assumes that the path overhead has been aligned with the first column following transport overhead.
Super STS-1 signals (STS-N) are formed by byte-multiplexing the N constituent STS-1 signals, with the resultant bandwidth being N times that of the STS-1 rate. Conversely, sub STS-1 signals are transported in Virtual Tributaries (VTs), of which four sizes are defined at present, namely VT1.5 (1.728 Mb/s), VT2 (2.304 Mb/s), VT3 (3.456 Mb/s) and VT6 (6.912 M/b/s). To accommodate mixes of VTs, the VT-structured STS-1 SPE is divided into 7 VT groups, with each group occupying 12 columns of the 9-row frame structure; 2 columns remain unused and are referred to as STUFF columns. A VT group may contain 4 VT1.5s, 3 VT2s, 2 VT3s, or 1 VT 6. Both the super STS and sub STS signals retain the frame rate of 125 .mu.s.
FIG. 2 shows a 3-dimensional representation of an STS-12 frame as an illustrative example. There are 12 vertical planes which represent the 12 STS-1s, each composed of 90 columns and 9 rows, for a total of 9720 bytes. Vertical columns may be grouped to form Virtual Tributaries (VTs), as shown by the four regularly-spaced columns representing a VT2 in position #3. While a VT2 requires 4 regularly-spaced columns, as shown, a VT1.5 requires 3 regularly-spaced columns, a VT3 requires 6 regularly-spaced columns, and a VT6 requires 12 regularly-spaced columns. Finally, a DS-0, corresponding to a 64 kilobits-per-second rate, appears as a single byte within one row and column. There are a maximum of 774 DS-0s per STS-1, some of which may be used for additional overhead functions; 756 DS-0s are available for traffic transport.
The three component sub-rates of an STS-N frame--STS-1, VT, and DS-0--may be switched independently by three separate switching fabrics, each dedicated to switching one of the sub-rates. But this is inefficient in the amount of equipment used: it requires demultiplexers at the inputs to the switching fabrics to separate the sub-rates, a separate switching fabric for each sub-rate, and multiplexers at the outputs from the switching fabrics to combine the switched sub-rates back into STS-N frames. The use of a single switching fabric for all sub-rates is therefore preferable.
Given a switching fabric capable of switching multiple rates within an STS-N format, one is faced with the problem of efficiently setting up multirate calls through such a fabric. One approach is to treat a call of any given bandwidth as multiple DS-0 calls. Although this is a flexible approach, the disadvantage is that a path-hunt and a path-setup must be performed individually for each DS-0 call. For example, a single STS-1 call would require as many as 810 individual path hunts and control-memory-setups. This is inefficient both in terms of the amount of time required for the path hunting and the number of control communications required to set up the individual paths.
Solution
The above problem is solved and a technical advance is achieved in accordance with the principles of the invention in a method of providing a switched connection of a given bandwidth through such a multiple-rate network where connections are provided at a high rate of a hierarchy of data rates to satisfy some of the given bandwidth--preferably as much of the given bandwidth as possible--thereby minimizing the number of path hunts and control communications required. Connections are then also provided at lower rates of the hierarchy to satisfy other, e.g., any remaining unsatisfied, of the given bandwidth. Hence, the connection of the given bandwidth is provided as a collection of a plurality of connections of smaller bandwidths of different sizes. Illustratively, the given bandwidth is divided into connections at the high rate, and any remainder of that bandwidth is divided into connections at the lower rate. An attempt is then made to provide the connections at the high rate. The bandwidth of any of the high-rate connections that fail to be made, e.g., because of unavailability of idle connections of this rate, is divided into additional connections at the lower rates. An attempt is then made to provide the lower-rate connections.
In an illustrative embodiment disclosed herein, the switching network is a three-stage network, such as a time-space-time network, and a hierarchy of status tables are stored for each input and each output switching element of the network. The tables have entries defining availability of time slots--representing bandwidth of the tables' corresponding rates--between the corresponding input or output switching element and an intermediate stage of the network. The hierarchy of status tables correspond to the hierarchy of data rates, and define availability as full (non-available), partial, or idle (fully available). Connections are provided at the high rate by finding matching idle entries in the high rate status tables across the intermediate stage, i.e., for the interface between the intermediate stage and the input and the output switching elements involved in the connection--referred to herein as status tables for the input and the output switching elements, for short. Connections are provided at a lower rate by finding matching entries that define at least partial availability in the high rate status tables for the input and the output switching elements and then finding matching idle entries in the corresponding lower-rate status tables. To maximize non-blocking performance, the path-hunt follows a search hierarchy for the lower-rate connections by first finding any matching partial entries in the high rate status tables for the input and the output switching elements. If sufficient partial entries cannot be found in the high rate status tables, or if sufficient idle entries cannot be found in the corresponding lower-rate status tables, further lower-rate connections are provided by finding corresponding partial/idle and idle/partial entries in the high data-rate status tables for the input and the output switching elements, and again finding matching idle entries in the corresponding lower-rate status tables. Finally, any remaining lower-rate connections are provided by finding corresponding idle entries in the high data-rate status tables for the input and the output switching elements, and finding matching idle entries in the corresponding lower-rate status tables. Thus, idle entries at the high data-rate are made unavailable for other connections at that rate only as a last resort, to prevent blocking. If the hierarchy of data rates comprises intermediate data rates, this search hierarchy is followed at every level of the hierarchy of status tables so as to preserve idle blocks of bandwidth at every level for use by connections of the highest possible data rate, whenever possible. Fragmenting of the idle bandwidth, into small fragments that would necessitate the making of connections of a given bandwidth as a collection of a larger-than-optimum number of smaller-than-optimum-size connections, is thereby minimized.
In a specific illustrative embodiment, the three-stage switching network provides connections at three types of rates: STS-1, VT, and DS-0. In addition, the intermediate rate type can be one or more of the VT1.5, VT2, VT3, or VT6 rates. The tables of the hierarchy of status tables correspond to the STS-1, VT and DS-0 data rates, and define availability as full, partial, or idle for the STS-1 and VT rates and define availability as busy or idle for the DS-0 data rate.
When an STS-1 connection is requested, matching idle entries are found in the STS-1 status tables for the input and the output switching elements to be used for the STS-1 connection. The time slots represented by the matching idle entries are assigned to the STS-1 connection. When matching idle entries are not found, an attempt is made to complete the STS-1 connection as a plurality of VT connections.
When a VT connection of an individual rate is requested, matching idle entries for the individual rate are found in the VT status tables for the input and the output switching elements. The time slots represented by the matching idle VT entries are assigned to the VT connection but only when the result of the assignment does not result in a previously-idle STS-1 entry no longer being available for STS-1 connections, unless such assignment is necessary to prevent blocking of the VT connection. When no time slots are assigned to the VT connection, an attempt is made to complete the VT connection as a plurality of DS-0 connections.
When a DS-0 connection is requested, matching idle entries are found in the DS-0 status tables for the input and the output switching elements. The time slots represented by the matching idle DS-0 entries are assigned to the DS-0 connection, but only when the result of the assignment does not result in a previously-idle VT entry no longer being available for VT connections, unless such assignment is necessary to prevent blocking of the DS-0 connection.
The invention minimizes the number of path-hunts that must be performed and the number of connections that must be set up to create a desired connection of a given bandwidth, yet does so without wasting bandwidth available for carrying other connections. It allows desired connections of substantially any bandwidth to be made, without sacrificing efficiency of path-hunting and connection-establishment and without sacrificing conservation of bandwidth. Furthermore, the invention utilizes available bandwidth in a most efficient manner, avoiding idle bandwidth fragmentation so as to minimize instances when a desired connection must be made as a collection of a greater-than-optimum number of smaller-than-optimum-size connections. Yet, at the same time, it provides flexibility in the composition of a desired connection so that the desired connection may be established as long as the given bandwidth is available, irrespective of the size and number of blocks into which that available bandwidth is fragmented.
These and other advantages and features of the invention will become apparent from the following description of an illustrative embodiment of the invention taken together with the drawing.